package top.ivansong92.example.leetcode.learning.other.string;

import org.junit.Test;

import java.util.*;

public class TestExamp2 {

    @Test
    public void testIsSubsequence() {
        System.out.println(isSubsequence("aaaaaa",
                "bbaaaa"));

    }

    /**
     * 392. 判断子序列
     *
     * @param s
     * @param t
     * @return
     */
    public boolean isSubsequence(String s, String t) {
        if (s == null || s.length() == 0) {
            return true;
        }

        int index = 0;
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            char ch = chars[i];
            int val = t.indexOf(ch, index);
            if (val < 0) {
                return false;
            }
            index = val + 1;
        }
        return true;
    }

    @Test
    public void testRomanToInt() {
        System.out.println(romanToInt("LVIII"));

    }

    /**
     * 13. 罗马数字转整数
     * I             1
     * V             5
     * X             10
     * L             50
     * C             100
     * D             500
     * M             1000
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/roman-to-integer
     *
     * @param s
     * @return
     */
    public int romanToInt(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int res = 0;
        char[] chars = s.toCharArray();
        char last = '0';
        for (int i = chars.length - 1; i >= 0; i--) {
            char ch = chars[i];
            switch (ch) {
                case 'I':
                    if (last == '0' || last == 'I') {
                        res += 1;
                        last = 'I';
                    } else if (last == 'V' || last == 'X') {
                        res -= 1;
                    } else {
                        return -1;
                    }
                    break;
                case 'V':
                    if (last == '0' || last == 'I' || last == 'V') {
                        res += 5;
                        last = 'V';
                    } else {
                        return -1;
                    }
                    break;
                case 'X':
                    if (last == '0' || last == 'I' || last == 'V' || last == 'X') {
                        res += 10;
                        last = 'X';
                    } else if (last == 'L' || last == 'C') {
                        res -= 10;
                    } else {
                        return -1;
                    }
                    break;
                case 'L':
                    if (last == '0' || last == 'I' || last == 'V' || last == 'X') {
                        res += 50;
                        last = 'L';
                    } else {
                        return -1;
                    }
                    break;
                case 'C':
                    if (last == '0' || last == 'I' || last == 'V' || last == 'X' || last == 'L' || last == 'C') {
                        res += 100;
                        last = 'C';
                    } else if (last == 'D' || last == 'M') {
                        res -= 100;
                    } else {
                        return -1;
                    }
                    break;
                case 'D':
                    if (last == '0' || last == 'I' || last == 'V' || last == 'X' || last == 'L' || last == 'C') {
                        res += 500;
                        last = 'D';
                    } else {
                        return -1;
                    }
                    break;
                case 'M':
                    if (last == '0' || last == 'I' || last == 'V' || last == 'X' || last == 'L' || last == 'C' || last == 'D' || last == 'M') {
                        res += 1000;
                        last = 'M';
                    } else {
                        return -1;
                    }
                    break;
                default:
                    return -1;
            }
        }
        return res;
    }

    private static final Map<Character, Integer> SYM_MAP = new HashMap<Character, Integer>() {{
        put('I', 1);
        put('V', 5);
        put('X', 10);
        put('L', 50);
        put('C', 100);
        put('D', 500);
        put('M', 1000);
    }};


    public int romanToInt1(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int res = 0;
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            char ch = chars[i];
            Integer val = SYM_MAP.get(ch);
            if (val == null) {
                return -1;
            }
            if (i < chars.length - 1) {
                Integer nextVal = SYM_MAP.get(chars[i + 1]);
                if (nextVal == null) {
                    return -1;
                }

                if (val.compareTo(nextVal) < 0) {
                    res -= val;
                } else {
                    res += val;
                }
            } else {
                res += val;
            }
        }
        return res;
    }

    @Test
    public void testIntToRoman() {
        System.out.println(intToRoman(4));
        System.out.println(intToRoman(8));
        System.out.println(intToRoman(9));

        System.out.println(intToRoman(10));
    }

    /**
     * 12. 整数转罗马数字
     * 罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。
     * <p>
     * 字符          数值
     * I             1
     * V             5
     * X             10
     * L             50
     * C             100
     * D             500
     * M             1000
     *
     * @param num
     * @return
     */
    private static final int[] SYM_VAL = new int[]{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    private static final String[] SYM = new String[]{"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

    public String intToRoman(int num) {
        if (num > 3999 || num <= 0) {
            return "";
        }
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < SYM.length; i++) {
            String sym = SYM[i];
            int val = SYM_VAL[i];
            while (num >= val) {
                num -= val;
                res.append(sym);
            }

            if (num <= 0) {
                break;
            }
        }
        return res.toString();
    }


    /**
     * 58. 最后一个单词的长度
     *
     * @param s
     * @return
     */
    public int lengthOfLastWord(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        String[] strings = s.split(" ");

        return strings[strings.length - 1].length();
    }

    public int lengthOfLastWord1(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        int res = 0;
        List<Character> tmp = new ArrayList<>();
        for(char ch : s.toCharArray()) {
            if (ch == ' ') {
                res = tmp.size() != 0 ? tmp.size() : res;
                tmp.clear();
            } else {
                tmp.add(ch);
            }
        }
        if (tmp.size() > 0) {
            res = tmp.size();
        }
        return res;
    }

    /**
     * 820. 单词的压缩编码
     * @param words
     * @return
     */
    public int minimumLengthEncoding(String[] words) {
        if (words == null || words.length == 0) {
            return 0;
        }
        Arrays.sort(words, Comparator.comparingInt(String::length).reversed());

        StringBuilder encodingRes = new StringBuilder(words[0] + "#");
        String wordIndex = words[0];
        for(int i = 1; i < words.length; i ++) {
            String word = words[i];
            if (word.length() > wordIndex.length()) {
                wordIndex = word;
                encodingRes.append(word).append("#");
                continue;
            }

            String subStr = word + "#";
            if (encodingRes.toString().contains(subStr)) {
                continue;
            }

            wordIndex = word;
            encodingRes.append(word).append("#");
        }
        return encodingRes.length();
    }

    @Test
    public void testMinimumLengthEncoding() {
        System.out.println(minimumLengthEncoding1(new String[]{}));
    }
    public int minimumLengthEncoding1(String[] words) {
        if (words == null || words.length == 0) {
            return 0;
        }

        if (words.length == 1) {
            return words[0].length() + 1;
        }

        String[] cpWords = new String[words.length];
        for(int i = 0; i < words.length; i ++) {
            cpWords[i] = new StringBuilder(words[i]).reverse().toString();
        }


        Arrays.sort(cpWords);
        String current = null, next = null;
        int res = 0;
        for(int i = 0; i < cpWords.length - 1; i ++) {
            current = cpWords[i];
            next = cpWords[i+1];
            if (next.length() < current.length()) {
                res += current.length() + 1;
                continue;
            }

            if (next.substring(0, current.length()).equals(current)) {
                continue;
            }
            res += current.length() + 1;
        }
        res += cpWords[cpWords.length - 1].length() + 1;
        return res;
    }


    /**
     * 3. 无重复字符的最长子串
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        int left = 0, right = 0, res = 1, len = s.length();

        char[] chars = s.toCharArray();
        Map<Character, Integer> chIndexMap = new HashMap<>();

        while (left < len && right < len) {
            if (left == right) {
                chIndexMap.clear();
                chIndexMap.put(chars[left], left);
                right ++;
                continue;
            }

            char ch = chars[right];
            Integer index = chIndexMap.get(ch);
            if (index != null) {
                if (left <= index) {
                    left = index + 1;
                }
                chIndexMap.remove(ch);
            } else {
                chIndexMap.put(ch, right);
                res = Math.max(right - left + 1, res);
                right ++;
            }
        }
        return res;
    }

    /**
     * 242. 有效的字母异位词
     * @param s
     * @param t
     * @return
     */
    public boolean isAnagram(String s, String t) {
        if (s == null || t == null || s.length() != t.length()) {
            return false;
        }

        int[] sCharCounter = new int[26];
        for (char ch : s.toCharArray()) {
            sCharCounter[ch - 'a'] += 1;
        }

        int[] tCharCounter = new int[26];
        for (char ch : t.toCharArray()) {
            tCharCounter[ch - 'a'] += 1;
        }

        for (int i = 0; i < 26; i++) {
            if (sCharCounter[i] != tCharCounter[i]) {
                return false;
            }
        }
        return true;
    }


    /**
     * 290. 单词规律
     * @param pattern
     * @param s
     * @return
     */
    public boolean wordPattern(String pattern, String s) {
        if (pattern == null || s == null) {
            return false;
        }

        char[] chars = pattern.toCharArray();
        String[] strings = s.split(" ");
        if (chars.length != strings.length) {
            return false;
        }

        Map<Character, String> chMap = new HashMap<>();
        Set<String> chValFilter = new HashSet<>();
        for (int i = 0; i < chars.length; i++) {
            char ch = chars[i];
            String word = chMap.get(ch);
            if (word == null) {
                word = strings[i];
                if (chValFilter.contains(word)) {
                    return false;
                }
                chValFilter.add(word);
                chMap.put(ch, word);
                continue;
            }

            if (!word.equals(strings[i])) {
                return false;
            }
        }

        return true;
    }

    /**
     * 205. 同构字符串
     * @param s
     * @param t
     * @return
     */
    public boolean isIsomorphic(String s, String t) {
        if (s == null && t == null) {
            return true;
        }

        if (s == null || t == null || s.length() != t.length()) {
            return false;
        }

        char[] sChars = s.toCharArray();
        char[] tChars = t.toCharArray();

        Map<Character, Character> chMap = new HashMap<>();
        Set<Character> chValFilter = new HashSet<>();
        for (int i = 0; i < sChars.length; i++) {
            char ch = sChars[i];
            Character w = chMap.get(ch);
            if (w == null) {
                w = tChars[i];
                if (chValFilter.contains(w)) {
                    return false;
                }
                chValFilter.add(w);
                chMap.put(ch, w);
                continue;
            }

            if (!w.equals(tChars[i])) {
                return false;
            }
        }
        return true;
    }
}
